namespace Offer0042MaxinumSubAry {

    /**
     * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
        要求时间复杂度为O(n)。

        示例1:
        输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
        输出: 6
        解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 
        提示：
        1 <= arr.length <= 10^5
        -100 <= arr[i] <= 100
     * @param nums 
     * @returns 
     */
    function maxSubArray(nums: number[]): number {
        // check the array
        if (!nums || nums.length == 0)
            return 0;
        // 动态规划求解(此题仅需要返回最大值即可)
        let pre = 0;// 之前连续序列的最大和
        let max = nums[0];//最大子数组和
        nums.forEach((v: number) => {
            pre = Math.max(pre + v, v);
            max = Math.max(max, pre);
        });
        return max;
    };

}